package com.example.demo.leetcode.top;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author xujimou
 * @date 2021/1/27 17:38
 **/
public class Linked_回文链表 {

    public boolean isPalindrome(ListNode head) {

        List<String> list = new ArrayList<>();
        while(head!=null){
            list.add(head.val+"");
            head = head.next;
        }
        String str = String.join(" ", list);

        String[] s1 = str.split(" ");
        int min = s1.length/2;
        if(s1.length % 2 ==0){
            for(int i=min-1,j=min;i>=0 && j<s1.length;i--,j++){
                if(!s1[i].equals(s1[j])){
                    return false;
                }
            }
            return true;
        }else{
            for(int i=min-1,j=min+1;i>=0 && j<s1.length;i--,j++){
                if(!s1[i].equals(s1[j])){
                    return false;
                }
            }
            return true;
        }

    }

    //使用栈翻转链表处理
    public static boolean isPalindrome2(ListNode head) {
        Stack<Integer> stack = new Stack<Integer>();
        ListNode head1 = head;
        while(head!=null){
            stack.push(head.val);
            head=head.next;
        }
        ListNode head2 = degui(stack);
        while(head1!=null && head2!=null){
            if(head1.val!=head2.val){
                return false;
            }
            head1=head1.next;
            head2=head2.next;
        }
        return true;
    }

    public static ListNode degui(Stack<Integer> stack){
        if(stack.isEmpty()){
            return null;
        }
        ListNode last = new ListNode(stack.pop());
        last.next=degui(stack);
        return last;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode head2 = new ListNode(2);
        head.next=head2;
        head2.next=null;
        isPalindrome2(head);
    }



    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

}
